home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / objtools / tlbsp.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  12KB  |  638 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    tlbsp -
  19.  *        BSP sort a triangle list
  20.  *
  21.  *            Paul Haeberli - 1991
  22.  */
  23. #include "stdio.h"
  24. #include "gl.h"
  25. #include "device.h"
  26. #include "trilist.h"
  27. #include "vect.h"
  28.  
  29. float fgetmousex();
  30. float fgetmousey();
  31.  
  32. #define USEDOUBLES
  33. #ifdef USEDOUBLES
  34.  
  35. #define FLOAT double
  36. #define V3F(v) v3d((double *)v)
  37. #define C3F(v) c3d((double *)v)
  38. #define VECT dvect
  39. #define VLERP dvlerp
  40. #define VDOT dvdot
  41. #define TRINORMAL dtrinormal
  42.  
  43. #else
  44.  
  45. #define FLOAT float
  46. #define V3F v3f
  47. #define C3F c3f
  48. #define VECT vect
  49. #define VLERP vlerp
  50. #define VDOT vdot
  51. #define TRINORMAL trinormal
  52.  
  53. #endif
  54.  
  55. #define TOLERANCE    0.000001
  56.  
  57. int dolines;
  58.  
  59. main(argc,argv)
  60. int argc;
  61. char **argv;
  62. {
  63.     short val;
  64.     FLOAT x, y;
  65.     int rendermode;
  66.  
  67.     if(argc<3) {
  68.     fprintf(stderr, "usage: tlbsp input.tl sort.tl\n");
  69.     exit(1);
  70.     }
  71.     foreground();
  72.     keepaspect(3,2);
  73.     winopen("tlbsp");
  74.     subpixel(1);
  75.     RGBmode();
  76.     gconfig();
  77.     cpack(0x00ffffff);
  78.     clear();
  79.     dolines = 0;
  80.     bspread(argv[1]);
  81.     bspsort();
  82.     bspdraw();
  83.     bsptofile(argv[2]);
  84.     exit(0);
  85. #ifdef DEBUG
  86.     qdevice(LEFTMOUSE);
  87.     qdevice(MIDDLEMOUSE);
  88.     qdevice(WKEY);
  89.     while(1) {
  90.     switch(qread(&val)){
  91.         case REDRAW:
  92.         bspdraw();
  93.         break;
  94.         case LEFTMOUSE:
  95.         if(val) {
  96.             dolines = 1-dolines;
  97.             bspdraw();
  98.         }
  99.         break;
  100.         case MIDDLEMOUSE:
  101.         if(val) {
  102.         }
  103.         break;
  104.         case WKEY:
  105.         if(val) {
  106.             x = 2.0*(fgetmousex()-0.5);
  107.             y = 2.0*(fgetmousey()-0.5);
  108.             printf("cur pos %f %f\n",x,y);
  109.         }
  110.         break;
  111.     }
  112.     }
  113. #endif
  114. }
  115.  
  116. /*
  117.  *    bsprender follows . . .
  118.  *
  119.  */
  120. #define TRITOL    (0.000001)
  121.  
  122. typedef struct bsptri {
  123.     struct bsptri *left, *right;
  124.     VECT p[3], c[3], n;
  125.     FLOAT d;
  126. } bsptri;
  127.  
  128. static bsptri *bsplist;
  129. static int bspnpoly, bspnsliver, bspinter;
  130. static int bspoutpolys, badsplit;
  131.  
  132. bsptri *sortbsplist();
  133.  
  134. bsptri *newtri()
  135. {
  136.     bsptri *tri;
  137.  
  138.     tri = (bsptri *)malloc(sizeof(bsptri));
  139.     tri->right = 0;
  140.     tri->left = 0;
  141.     return tri;
  142. }
  143.  
  144. cpacktov(c,v)
  145. long c;
  146. VECT *v;
  147. {
  148.     v->x = ((c>>0)&0xff)/255.0;
  149.     v->y = ((c>>8)&0xff)/255.0;
  150.     v->z = ((c>>16)&0xff)/255.0;
  151.     v->w = ((c>>24)&0xff)/255.0;
  152. }
  153.  
  154. bspread(name)
  155. char *name;
  156. {
  157.     int i, ntri;
  158.     trilisttri tltri;
  159.     bsptri *tri;
  160.     VECT norm, p0, p1, p2;
  161.  
  162.     ntri = tlopen(name);
  163.     bsplist = 0;
  164.     bspnpoly = 0;
  165.     bspnsliver = 0;
  166.     for(i=0; i<ntri; i++) {
  167.     tlread(&tltri);
  168.     p0.x = tltri.x0;
  169.     p0.y = tltri.y0;
  170.     p0.z = tltri.z0;
  171.     p1.x = tltri.x1;
  172.     p1.y = tltri.y1;
  173.     p1.z = tltri.z1;
  174.     p2.x = tltri.x2;
  175.     p2.y = tltri.y2;
  176.     p2.z = tltri.z2;
  177.     if(TRINORMAL(&p0,&p1,&p2,&norm,TRITOL)) {
  178.         tri = newtri();
  179.         tri->p[0] = p0;
  180.         cpacktov(tltri.c0,&tri->c[0]);
  181.         tri->p[1] = p1;
  182.         cpacktov(tltri.c1,&tri->c[1]);
  183.         tri->p[2] = p2;
  184.         cpacktov(tltri.c2,&tri->c[2]);
  185.         tri->n.x = norm.x;
  186.         tri->n.y = norm.y;
  187.         tri->n.z = norm.z;
  188.         tri->d = VDOT(&p0,&norm);
  189.         tri->left = bsplist;
  190.         bsplist = tri;
  191.         bspnpoly++;
  192.         } else {
  193.         bspnsliver++;
  194.     }
  195.     }
  196.     tlclose();
  197.     printf("bspread: npolys %d nsliver %d\n",bspnpoly,bspnsliver);
  198. }
  199.  
  200. bspsort()
  201. {
  202.     bspinter = 0;
  203.     badsplit = 0;
  204.  
  205.     bsplist = sortbsplist(bsplist,bspnpoly,0);
  206.     printf("bspsort: n intersect %d\n",bspinter);
  207.     printf("bspsort: n bad split %d\n",badsplit);
  208.  
  209. }
  210.  
  211. bspdraw()
  212. {
  213.     reshapeviewport();
  214.     ortho(-1.0,1.0,-1.0,1.0,-2.0,2.0);
  215.     cpack(0x00ffffff);
  216.     clear();
  217.     bspoutpolys = 0;
  218.     drawbsplist(bsplist);
  219.     printf("bspdraw: output polygons %d\n",bspoutpolys);
  220. }
  221.  
  222. bsptofile(name)
  223. char *name;
  224. {
  225.     short magic;
  226.     FILE *outf;
  227.  
  228.     outf = fopen(name,"w");
  229.     if(!outf) {
  230.     fprintf(stderr,"tlbsp: can't open output file\n");
  231.     exit(1);
  232.     }
  233.     magic = TLMAGIC;
  234.     fwrite(&magic,sizeof(short),1,outf);
  235.     writebsplist(outf,bsplist);
  236.     fclose(outf);
  237. }
  238.  
  239. bspfree()
  240. {
  241.     freebsplist(bsplist);
  242.     bsplist = 0;
  243. }
  244.  
  245. #define E0    0x1
  246. #define E1    0x2
  247. #define E2    0x4
  248.  
  249. checksplit(list,split,intersect,nleft,nright)
  250. bsptri *list, *split;
  251. int *intersect, *nleft, *nright;
  252. {
  253.     bsptri *try;
  254.     FLOAT d, dm, dp;
  255.     FLOAT pd[3];
  256.  
  257.     *intersect = 0;
  258.     *nleft = 0;
  259.     *nright = 0;
  260.     d = split->d;
  261.     dm = d-TOLERANCE;
  262.     dp = d+TOLERANCE;
  263.     try = list;
  264.     while(try) {
  265.     if(try != split) {
  266.         pd[0] = VDOT(&split->n,&try->p[0]);
  267.         pd[1] = VDOT(&split->n,&try->p[1]);
  268.         pd[2] = VDOT(&split->n,&try->p[2]);
  269.         if(pd[0]<dp && pd[1]<dp && pd[2]<dp)
  270.         (*nleft)++;
  271.         else if(pd[0]>dm && pd[1]>dm && pd[2]>dm)
  272.         (*nright)++;
  273.         else 
  274.         (*intersect)++;
  275.     }
  276.     try = try->left;
  277.     }
  278. }
  279.  
  280. bsptri *sortbsplist(l,unsorted,level)
  281. bsptri *l;
  282. int unsorted, level;
  283. {
  284.     int i, p;
  285.     bsptri *split, *try, *next;
  286.     bsptri *left, *right;
  287.     bsptri *newl, *bestsplit;
  288.     int leftun, rightun;
  289.     FLOAT d, dm, dp, param;
  290.     FLOAT pd[3];
  291.     int sign[3];
  292.     int intercode, vr, v0, v1, v2;
  293.     VECT ip0, ip1;
  294.     VECT ic0, ic1;
  295.     int checkn, checkl, checkr;
  296.     FLOAT mininter, frac;
  297.  
  298.     if(level<6) {
  299.      for(i=0; i<level; i++)
  300.          fprintf(stderr,"    ");
  301.      fprintf(stderr,"at level %d: %d\n",level,unsorted); 
  302.     }
  303.     if(!l)
  304.     return 0;
  305.     if(unsorted<=1)
  306.     return l;
  307.  
  308. /* figure out a sliting plane */
  309.     if(unsorted<25) {
  310.     split = l;
  311.     bestsplit = split;
  312.     mininter = unsorted;
  313.     while(split) {
  314.         checksplit(l,split,&checkn,&checkl,&checkr);
  315.         frac = checkl-checkr;
  316.         if(frac<0.0)
  317.         frac = -frac;
  318.         frac = checkn+(frac/unsorted);
  319.         if(mininter>frac) {
  320.         mininter = frac;
  321.         bestsplit = split;
  322.         }
  323.         split = split->left;
  324.     }
  325.     if(!split) {
  326. /* printf("BEST %f\n",mininter); */
  327.         split = bestsplit;
  328.     }
  329.     } else {
  330.     p = rand()%unsorted;
  331.     split = l;
  332.     for(i=0; i<p; i++) {
  333.         split = split->left;
  334.     }
  335.     }
  336.     left = right = 0;
  337.     leftun = rightun = 0;
  338.  
  339.     d  = split->d;
  340.     dm = d-TOLERANCE;
  341.     dp = d+TOLERANCE;
  342.     try = l;
  343.     while(try) {
  344.     next = try->left;
  345.     if(try != split) {
  346.         pd[0] = VDOT(&split->n,&try->p[0]);
  347.         pd[1] = VDOT(&split->n,&try->p[1]);
  348.         pd[2] = VDOT(&split->n,&try->p[2]);
  349.         if(pd[0]<dp && pd[1]<dp && pd[2]<dp) {
  350.         try->left = left;
  351.         left = try;
  352.         leftun++;
  353.         } else if(pd[0]>dm && pd[1]>dm && pd[2]>dm) {
  354.         try->left = right;
  355.         right = try;
  356.         rightun++;
  357.         } else {
  358.         bspinter++;
  359.         intercode = 0;
  360.         if(pd[0]<d && pd[1]>d) {
  361.             intercode |= E0;
  362.             sign[0] = 1;
  363.         } else if(pd[0]>d && pd[1]<d) {
  364.             intercode |= E0;
  365.             sign[0] = 0;
  366.         }
  367.         if(pd[1]<d && pd[2]>d) {
  368.             intercode |= E1;
  369.             sign[1] = 1;
  370.         } else if(pd[1]>d && pd[2]<d) {
  371.             intercode |= E1;
  372.             sign[1] = 0;
  373.         }
  374.         if(pd[2]<d && pd[0]>d) {
  375.             intercode |= E2;
  376.             sign[2] = 1;
  377.         } else if(pd[2]>d && pd[0]<d) {
  378.             intercode |= E2;
  379.             sign[2] = 0;
  380.         }
  381.         vr = 0;
  382.         switch(intercode) {
  383.             case E2:
  384.             vr++;
  385.             case E1:
  386.             vr++;
  387.             case E0:
  388.             v0 = (0+vr)%3;
  389.             v1 = (1+vr)%3;
  390.             v2 = (2+vr)%3;
  391.             param = (d-pd[v0])/(pd[v1]-pd[v0]);
  392.             VLERP(&try->p[v0],&try->p[v1],&ip0,param);
  393.             VLERP(&try->c[v0],&try->c[v1],&ic0,param);
  394.  
  395.             newl = newtri();        /* neg side */
  396.             newl->p[v0] = try->p[v0];
  397.             newl->c[v0] = try->c[v0];
  398.             newl->p[v1] = ip0;
  399.             newl->c[v1] = ic0;
  400.             newl->p[v2] = try->p[v2];
  401.             newl->c[v2] = try->c[v2];
  402.             newl->n = try->n;
  403.             newl->d = try->d;
  404.             if(sign[v0]) {
  405.                 newl->left = left;
  406.                 left = newl;
  407.                 leftun++;
  408.             } else {
  409.                 newl->left = right;
  410.                 right = newl;
  411.                 rightun++;
  412.             }
  413.  
  414.             newl = newtri();        /* pos side */
  415.             newl->p[v0] = ip0;    
  416.             newl->c[v0] = ic0;    
  417.             newl->p[v1] = try->p[v1];
  418.             newl->c[v1] = try->c[v1];
  419.             newl->p[v2] = try->p[v2];
  420.             newl->c[v2] = try->c[v2];
  421.             newl->n = try->n;
  422.             newl->d = try->d;
  423.             if(sign[v0]) {
  424.                 newl->left = right;
  425.                 right = newl;
  426.                 rightun++;
  427.             } else {
  428.                 newl->left = left;
  429.                 left = newl;
  430.                 leftun++;
  431.             }
  432.             free(try);
  433.  
  434.             break;
  435.  
  436.             case E2|E0:
  437.             vr++;
  438.             case E1|E2:
  439.             vr++;
  440.             case E0|E1:
  441.             v0 = (0+vr)%3;
  442.             v1 = (1+vr)%3;
  443.             v2 = (2+vr)%3;
  444.             param = (d-pd[v0])/(pd[v1]-pd[v0]);
  445.             VLERP(&try->p[v0],&try->p[v1],&ip0,param);
  446.             VLERP(&try->c[v0],&try->c[v1],&ic0,param);
  447.             param = (d-pd[v2])/(pd[v1]-pd[v2]);
  448.             VLERP(&try->p[v2],&try->p[v1],&ip1,param);
  449.             VLERP(&try->c[v2],&try->c[v1],&ic1,param);
  450.  
  451.             newl = newtri();        /* neg side */
  452.             newl->p[v0] = try->p[v0];
  453.             newl->c[v0] = try->c[v0];
  454.             newl->p[v1] = ip0;
  455.             newl->c[v1] = ic0;
  456.             newl->p[v2] = try->p[v2];
  457.             newl->c[v2] = try->c[v2];
  458.             newl->n = try->n;
  459.             newl->d = try->d;
  460.             if(sign[v0]) {
  461.                 newl->left = left;
  462.                 left = newl;
  463.                 leftun++;
  464.             } else {
  465.                 newl->left = right;
  466.                 right = newl;
  467.                 rightun++;
  468.             }
  469.  
  470.             newl = newtri();        /* neg side */
  471.             newl->p[v0] = ip0;
  472.             newl->c[v0] = ic0;
  473.             newl->p[v1] = ip1;
  474.             newl->c[v1] = ic1;
  475.             newl->p[v2] = try->p[v2];
  476.             newl->c[v2] = try->c[v2];
  477.             newl->n = try->n;
  478.             newl->d = try->d;
  479.             if(sign[v0]) {
  480.                 newl->left = left;
  481.                 left = newl;
  482.                 leftun++;
  483.             } else {
  484.                 newl->left = right;
  485.                 right = newl;
  486.                 rightun++;
  487.             }
  488.  
  489.             newl = newtri();        /* pos side */
  490.             newl->p[v0] = ip0;
  491.             newl->c[v0] = ic0;
  492.             newl->p[v1] = try->p[v1];
  493.             newl->c[v1] = try->c[v1];
  494.             newl->p[v2] = ip1;
  495.             newl->c[v2] = ic1;
  496.             newl->n = try->n;
  497.             newl->d = try->d;
  498.             if(sign[v0]) {
  499.                 newl->left = right;
  500.                 right = newl;
  501.                 rightun++;
  502.             } else {
  503.                 newl->left = left;
  504.                 left = newl;
  505.                 leftun++;
  506.             }
  507.             free(try);
  508.  
  509.             break;
  510.  
  511.             default:
  512.             printf("strange code %d\n",intercode);
  513.             badsplit++;
  514.         }
  515.         }
  516.     }
  517.     try = next;
  518.     }
  519.     split->left = sortbsplist(left,leftun,level+1);
  520.     split->right = sortbsplist(right,rightun,level+1);
  521.     return split;
  522. }
  523.  
  524. freebsplist(l)
  525. bsptri *l;
  526. {
  527.     if(l->left)
  528.     freebsplist(l->left);
  529.     if(l->right)
  530.     freebsplist(l->right);
  531.     if(l) 
  532.     free(l);
  533. }
  534.  
  535. drawbsplist(l)
  536. bsptri *l;
  537. {
  538.     bsptri *a, *b;
  539.  
  540.     if(!l)
  541.     return;
  542.     if(l->n.z > 0.0) {
  543.     a = l->left;
  544.     b = l->right;
  545.     } else {
  546.     b = l->left;
  547.     a = l->right;
  548.     }
  549.     if(a)
  550.     drawbsplist(a);
  551.     bspoutpolys++;
  552.     if(dolines) {
  553.     cpack(0x00ffffff);
  554.     bgnpolygon();
  555.     V3F(&l->p[0]);
  556.     V3F(&l->p[1]);
  557.     V3F(&l->p[2]);
  558.     endpolygon();
  559.     cpack(0x00000000);
  560.     bgnclosedline();
  561.     V3F(&l->p[0]);
  562.     V3F(&l->p[1]);
  563.     V3F(&l->p[2]);
  564.     endclosedline();
  565.     } else {
  566.     bgnpolygon();
  567.     C3F(&l->c[0]);
  568.     V3F(&l->p[0]);
  569.     C3F(&l->c[1]);
  570.     V3F(&l->p[1]);
  571.     C3F(&l->c[2]);
  572.     V3F(&l->p[2]);
  573.     endpolygon();
  574.     }
  575.     if(b)
  576.     drawbsplist(b);
  577. }
  578.  
  579. unsigned long vecttocpack( v )
  580. VECT *v;
  581. {
  582.     int r, g, b, a;
  583.     unsigned long c;
  584.  
  585.     r = 255.0*v->x;
  586.     g = 255.0*v->y;
  587.     b = 255.0*v->z;
  588.     a = 255.0*v->w;
  589.     c =  (a<<24) + (b<<16) + (g<<8) + (r<<0);
  590.     return c;
  591. }
  592.  
  593. writebsplist(outf,l)
  594. FILE *outf;
  595. bsptri *l;
  596. {
  597.     bsptri *a, *b;
  598.     trilisttri tltri;
  599.  
  600.     if(!l)
  601.     return;
  602.     if(l->n.z > 0.0) {
  603.     a = l->left;
  604.     b = l->right;
  605.     } else {
  606.     b = l->left;
  607.     a = l->right;
  608.     }
  609.     if(a)
  610.     writebsplist(outf,a);
  611.     tltri.x0  = l->p[0].x;
  612.     tltri.y0  = l->p[0].y;
  613.     tltri.z0  = l->p[0].z;
  614.     tltri.c0 = vecttocpack(l->c+0);
  615.     tltri.x1  = l->p[1].x;
  616.     tltri.y1  = l->p[1].y;
  617.     tltri.z1  = l->p[1].z;
  618.     tltri.c1 = vecttocpack(l->c+1);
  619.     tltri.x2  = l->p[2].x;
  620.     tltri.y2  = l->p[2].y;
  621.     tltri.z2  = l->p[2].z;
  622.     tltri.c2 = vecttocpack(l->c+2);
  623.     fwrite(&tltri,sizeof(trilisttri),1,outf);
  624.     if(b)
  625.     writebsplist(outf,b);
  626. }
  627.  
  628. c3d(d)
  629. double d[3];
  630. {
  631.     float f[3];
  632.  
  633.     f[0] = d[0];
  634.     f[1] = d[1];
  635.     f[2] = d[2];
  636.     c3f(f);
  637. }
  638.